Cite this Article
Cai Ning, Chen Zhe-Bo, Cao Xiang-Qun, Lin Bin. Optimized dithering technique in frequency domain for high-quality three-dimensional depth data acquisition. Chinese Physics B, 2019, 28(8): 084202  
Permissions
Optimized dithering technique in frequency domain for high-quality three-dimensional depth data acquisition
Cai Ning1, 2, Chen Zhe-Bo2, Cao Xiang-Qun1, Lin Bin1, 2, †
State Key Laboratory of Modern Optical Instrumentation, CNERC for Optical Instruments, Zhejiang University, Hangzhou 310027, China
Research Institute of Zhejiang University-Taizhou, Taizhou 318000, China

 

† Corresponding author. E-mail: wjlin@zju.edu.cn

Abstract

On the basis of the objective functions, dithering optimization techniques can be divided into the intensity-based optimization technique and the phase-based optimization technique. However, both types of techniques are spatial-domain optimization techniques, while their measurement performances are essentially determined by the harmonic components in the frequency domain. In this paper, a novel genetic optimization technique in the frequency domain is proposed for high-quality fringe generation. In addition, to handle the time-consuming difficulty of genetic algorithm (GA), we first optimize a binary patch, then join the optimal binary patches together according to periodicity and symmetry so as to generate a full-size pattern. It is verified that the proposed technique can significantly enhance the measured performance and ensure the robustness to various amounts of defocusing.

PACS: 42.30.-d;42.62.Eh;06.30.Ft;42.30.Rx
Keyword:fringe generation;genetic algorithm;frequency domain;3D shape measurement
1. Introduction

Three-dimensional (3D) depth data acquisition techniques are becoming increasingly important for video game design, animation, movies, virtual reality, telesurgery, medicine, homeland security and manufacturing.[1] Among these techniques, the digital fringe projection (DFP) techniques have the great potential to be an integrated part of intelligent systems due to their simplicity, reliability and flexibility.[2] To reconstruct the 3D depth data, the DFP technique utilizes a projector to project a sequence of sinusoidal phase-shifted fringe patterns onto the surface of an object, and a camera to capture the deformed fringe patterns.[3] However, the conventional DFP technique needs 8 bits to present sinusoidal fringes, which is limited by a projector’s frame rate (typically Hz). In addition, the projector nonlinearity can introduce phase errors, if a commercial video projector is used.[4,5]

To break the speed limitation, the binary defocusing techniques[6,7] were introduced, with which a properly defocused binary pattern is considered as a sinusoidal pattern in a good approximation. Based on the structure of digital micro-mirror device (DMD), we are able to present the binary patterns by simply toggling DMD, which can improve the frame rate.[8] Moreover, the 1-bit depth of a binary pattern can eliminate the projector nonlinearity error easily. However, the measurement quality based on the binary defocusing technique is not comparable to that from the conventional DFP technique due to the harmonic errors.[9,10]

The squared binary defocusing method (SBM) was proposed at the very beginning.[11] Later, sinusoidal pulse width modulation (SPWM),[12] optimal pulse width modulation (OPWM),[13] and tripolar OPWM[14] were proposed and developed to reduce the harmonics errors. These techniques can achieve good performance with narrow fringe stripes, but all fail to produce high-precision defocused sinusoidal fringes with long fringe periods. These modulation techniques are one-dimensional techniques, which cannot take advantage of two-dimensional characteristics of a binary pattern.

The dithering technique,[15] which is also called halftoning, takes advantage of two-dimensional characteristics and was introduced to enhance the phase quality for wide fringe stripes. However, the improvements have still been limited by narrow fringe stripes.[16] Since dithering technique is only a simple matrix transformation, the measurement quality has great room to be improved. Dithering optimization techniques are introduced for a DFP system with defocused projectors. On the basis of the objective function, the previous techniques can be divided into the intensity-based optimization technique[17] and the phase-based optimization technique.[18] These two techniques are referred to as i-opt and p-opt hereafter, respectively. The p-opt technique can obtain better performance, while the phase quality directly determines the measurement performance. However, the different sensitivities to different amounts of defocusing make the p-opt technique troublesome to use. Although the i-opt technique cannot improve the measurement quality directly nor efficiently, it ensures the robustness to different amounts of defocusing. The two techniques can achieve pretty good measurement results, and they are both spatial-domain optimized. Since the most troublesome noise is induced by the high-frequency harmonics, it is necessary to optimize a binary pattern based on the frequency to improve the measurement quality.

The genetic algorithm (GA)[19] is an evolutionary algorithm on the basis of the theory of natural selection. The GA is a non-deterministic global optimization well suitable for binary fringe generation, which iterates through selection, crossover and mutation stages. A genetic method[20] was proposed to optimize the dithering technique. However, it is a time-consuming process to achieve good measurement quality.

In this paper, a genetic optimization framework in the frequency domain is proposed, which essentially improves the measurement quality by eliminating the harmonic errors. In view of the fact that defocusing amount is continuous in reality, our framework optimizes the binary pattern not only at a certain amount of defocusing. On the basis of the periodicity and symmetry property of sinusoidal pattern, we search a best binary patch instead of the whole pattern to handle the time-consuming difficulty of GA. The optimal patch is then tied together to generate the whole pattern. It is verified that the proposed technique is able to consistently obtain higher measurement performance under various amounts of defocusing.

Some related principles of the proposed technique are introduced in Section 2. In Section 3, our genetic optimization framework based on frequency domain is presented. Simulations and experiments are given in Sections 4 and 5, respectively. Finally, we summarize the findings in this paper in Section 6.

2. Principle
2.1. Three-step phase-shifting algorithm

Phase-shifting algorithms have been increasingly utilized in a DFP system due to their high measurement accuracy and flexibility.[21] Typically, these algorithms obtain better 3D measurement result with more fringe images. A minimal number of fringe patterns is required in a three-step phase-shifting algorithm with a phase shift of 2π / 3. The intensities of these sinusoidal fringe patterns can be described as

Here, Ia denotes the average intensity, Im symbolizes the modulation intensity, and φ represents the pixel-wise phase map to be solved and can be expressed as
Equation (4) yields phase values in a range [−π, +π) with 2π discontinuity. Using a temporal or spatial phase unwrapping algorithm, the continuous phase map is achieved.[22]

2.2. Error-diffusion dithering techniques

Dithering techniques used in computer graphics are introduced to represent a color depth pattern with a limited bit depth.[23] To approximate an ideal sinusoidal pattern with a binary pattern, a variety of dithering algorithms have been proposed, such as error-diffusion dithering, pattering dithering, simple thresholding, ordered dithering and random dithering.[16] The error-diffusion dithering algorithm has been widely utilized due to its high accuracy. For an error-diffusion algorithm, it adopts an error diffusion kernel d(i,j) to quantize pixels in a specified order, and it then compensates for the quantization error through the use of feedback. The process is shown as

where denotes the quantized image, I(x,y) symbolizes the original image, and e(x,y) is the difference taken from the diffused image and the quantized image, called quantization error. By using the diffusion kernel d(i,j), e(x,y) is further diffused into its adjacent regions. Typically, Floyd–Steinberg kernel is utilized for the error-diffusion dithering algorithm, which can be described as
where, the symbol denotes the pixel being process, symbolizing the previously processed pixel.

2.3. Two-dimensional discrete Fourier transform

Two-dimensional discrete Fourier transform (DFT2) is often used in mathematical imaging and vision. The DFT2 of an M × N image f(x,y), can be described as

Here, F(u,v) is the coefficient matrix in frequency domain, .

To reduce the computation time of DFT2, two-dimensional fast Fourier transform algorithm (FFT2) containing a variety of tricks is proposed.[24] The FFT2 can push the algorithm complexity from N 2 into . In this paper, FFT2 is used to transform spatial domain data into frequency domain data.

3. Optimization based on frequency domain
3.1. Frequency-based objective function for optimization

The key issue of the binary defocusing technique is how to produce binary patterns which can imitate the original sinusoidal patterns well after being defocused by a projector. The previously proposed techniques all optimized a binary pattern based on the spatial domain. Actually, the harmonic components in the frequency domain essentially determine the measurement quality. A sinusoidal fringe pattern is shown in Fig. 1(a). Figure 1(b) shows a binary fringe pattern using Floyd–Steinberg error-diffusion dithering algorithm. Figures 1(c) and 1(d) show the frequency spectra of the two patterns. The frequency errors of the two patterns are shown in Fig. 1(e). The magnitude in the frequency spectrum is normalized. From these results, it is found that the dithered pattern contains a little of low-frequency noise and lots of high-frequency noise.

Fig. 1. Frequency spectrum of ideal fringe pattern and binary pattern obtained by Floyd–Steinberg error-diffusion dithering algorithm. (a) Ideal pattern, (b) Floyd–Steinberg error-diffusion dithered pattern, (c) frequency spectrum of an ideal sinusoidal fringe pattern, (d) frequency spectrum of Floyd–Steinberg error-diffusion dithered pattern, (e) frequency error of the two patterns.

Our proposed method translates the process of optimization from the spatial domain to the frequency domain. Its aim is to search an optimal binary fringe to approximate the sinusoidal fringe in the frequency domain, so the problem is formulated as

where represents the L2 norm, FFT2() denotes two-dimensional fast Fourier transform, Ef represents the frequency error, S denotes the sinusoidal pattern, G symbolizes the Gaussian kernel which is the blurring function, is the 2D convolution, and B represents the binary pattern.

In view of the fact that defocusing amount is continuous in reality, our framework optimizes the binary patch not only at one certain amount of defocusing. Let S be the sinusoidal patch, and P be the patch to be optimized. The approximation error in the frequency domain with a certain sized Gaussian filter can be defined as

where M × N represents the size of P and S, Gt denotes a t × t Gaussian filter with a standard deviation of t/3, and is the frequency difference between the defocusing binary patch and the sinusoidal patch.

Gaussian filters of 5 × 5, 9 × 9, and 13 × 13 are, respectively, modeled as nearly focused, slightly defocused, and severely defocused projectors. To make the measurement quality robust to various amounts of defocusing, the frequency error should be minimized at various amounts of defocusing. Mathematically, the objective function can be selected as

3.2. Genetic optimization framework

The GA was first introduced by John Holland in the 1960s.[19] According to the theory of natural selection, the iteration of GA has different stages including selection, crossover and mutation.[25] The solutions are called chromosomes. Chromosomes are reproduced by crossover and mutation to create a new generation.[26]

To solve the time-consuming problem, we search an optimal binary patch, not the full-size pattern. The optimal binary patch is then tiled together according to periodicity and symmetry to generate a full-size pattern. Assuming that the sinusoidal fringe is vertical, the binary fringe should be symmetric about the horizontal direction and periodic along both horizontal and vertical directions. Figure 2 shows the flowchart of optimization steps described below.

Fig. 2. Flowchart of optimization steps.

Step 1 Individual formation. The binary patch is extracted as , where and denote the column period and the row period, respectively. T represents the fringe period. The individual is set to be a one-dimensional array with a length of .

Step 2 Population initialization. The proposed GA is designed to have a population of 50 patches. In general, a better initial estimate can lead to a better final solution. In view of this, we utilize the error-diffusion dither patterns to create the initial values. Different patches can be formed according to path- and origin-dependent property of the error-diffusion algorithm. Among the patches, four patches are respectively extracted from the error-diffusion dither patterns starting from the top left-hand corner, the top right-hand corner, the bottom left-hand corner, and the bottom right-hand corner, and the other patches are typically randomly initialized.

Step 3 Fitness evaluation. Individuals are evaluated by the fitness function described in Eq. (10).

Step 4 Selection. Individuals with better fitness are more likely to be selected as parents. The selection function adopts the stochastic uniform method.

Step 5 Crossover. Crossover is used to exchange information. Those parents with good performance are selected for recombination to generate new individuals. A random position and a random length is chosen, and the region which has a larger error is more likely to be chosen with a 50% higher probability to avoid wasting too much time.

Step 6 Mutation. Mutation operator introduces the random changes into the characteristics of individuals. We set the rate to be 1%, and the regions with higher errors undergo mutating more than 50% of the time as crossover.

Step 7 Iteration. If the stopping criterion is not satisfied, go back to Step 3. In this paper, the stopping criterion is that the average change of the fitness is less than 1e−6, or the iteration is more than 10000 times.

Step 8 Individual dimension mutation. Change , , and go back to Step 2.

Step 9 Patch generation. Select the best individual to generate the optimal patch from the optimized individuals, which minimizes Eq. (10) at a certain value of .

Step 10 Full-size fringe pattern generation. The optimal binary patch can be tied together according to periodicity and symmetry to generate a full-size pattern.

4. Simulations

Simulations were implemented to evaluate the superiority of the proposed technique with a wide range of fringe periods. In these simulations, fringe patterns (resolution 1024 × 768) with fringe periods T = 18, 36, …, 90, 108 were used to ensure practicability. Various amounts of defocusing were simulated by adopting Gaussian filter with different values of size G and standard deviation σ (G = 5∼17, and σ = G/3). A three-step phase-shifting algorithm is used to calculate the phase map, and the phase RMS error was achieved between the phase acquired from the ideal sinusoidal patterns and that from the blurred binary patterns. To compare the difference, the phase errors obtained from the i-opt[17] fringes and those from the p-opt[18] fringes were also evaluated. The two optimization methods are both optimized on condition that G = 5, and σ = G/3.

The desired ideal sinusoidal pattern and binary patterns obtained by adopting the optimization methods are shown in Fig. 3. The desired sinusoidal fringe with period T = 36 is shown in Fig. 3(a). The binary fringes generated by using the p-opt technique, the i-opt technique and the proposed technique, respectively, are shown in Figs. 3(b)–3(d). Figure 3(e) shows the cross-sections of the sinusoidal pattern and the three binary patterns.

Fig. 3. Binary patterns generated by different techniques, showing (a) desired sinusoidal fringe with period T = 36, (b) p-opt binary fringe, (c) i-opt binary fringe, (d) proposed optimization binary fringe, and (e) cross-sections of sinusoidal pattern and three binary patterns.

Figure 4 shows a comparison of different techniques. Figure 4(a) shows the cross-sections associated with an ideal sinusoidal pattern and three defocusing binary patterns shown in Figs. 3(b)–3(d). One can see that the results from the proposed technique and the i-opt technique are closer to the ideal sinusoidal curve than those from the p-opt technique. Although the i-opt technique is a little closer to the ideal sinusoidal curve, the proposed technique is more sinusoidal. Figures 4(b) and 4(c) show the normalized spectra errors associated with the above techniques. The high-frequency components of a signal can be eliminated after applying Gaussian filter, while the low-frequency components cannot. It can be seen that the p-opt technique still contains a large number of low-frequency components, which causes the sensitivities to various amounts of defocusing. In contrast, the proposed technique and the i-opt technique contain a small number of low-frequency components. And the frequency spectrum error of the proposed technique is smaller than that from the i-opt technique not only in the high-frequency region but also in the low-frequency region.

Fig. 4. Comparison of different techniques. (a) Cross-sections of sinusoidal pattern and three defocusing binary patterns respectively shown in Figs. 3(b)–3(d). (b) and (c) Normalized frequency spectra errors associated with the p-opt technique, the i-op technique and the proposed technique, respectively.

Figure 5 shows phase RMS error comparison associated with the three optimization techniques. By analyzing the simulations, we can observe that the p-opt technique can achieve best measurement performance when the Gaussian filter size G = 5. However, the measurement performance of p-opt technique deteriorates and becomes worse than that from the proposed technique and the i-opt technique especially with narrow fringe stripes. In contrast, the proposed technique and the i-opt technique consistently improve measurement quality. The phase error of the proposed technique and the i-opt technique decrease with the Gaussian filter size increasing. In most of cases, the proposed technique obtains better measurement performance than the other two techniques. It is shown that the proposed technique is able to persistently produce high-performance binary patterns for various amounts of defocusing.

Fig. 5. Phase RMS errors of p-opt technique, i-opt technique, and proposed technique with different Gaussian sizes and fringe periods T.
5. Experiments

Experiments were conducted to verify the proposed technique using a 3D shape measurement system including a Daheng mercury camera (MER-130-30UM) with an 8-mm focal length megapixel lens (Computar M0814-MP2) and a projector (Esonic HD-720P). The projector has a resolution of 1280 × 720, and the image has a resolution of 1024 × 768. Figure 6 shows the 3D shape measurement system.

Fig. 6. 3D shape measurement system.

First, an experiment was conducted to measure a flat white board by using the p-opt technique, the i-opt technique and the proposed technique. The phase errors were obtained between the phases recovered from the ideal phase and defocused binary patterns. The ideal phase was obtained from the measurement results of sinusoidal fringes with 18-step phase-shifting algorithm. The phase RMS errors achieved by different optimization techniques with various amounts of defocusing are shown in Fig. 7. It can be noticed that the p-opt technique only achieve relatively competitive performance, if the nearly-focused projector is used. With the amount of defocusing increasing, the measurement quality of the p-opt technique becomes worse than that of the proposed technique and the i-opt technique especially when narrow fringe stripes are utilized. In addition, the proposed technique can outperform the i-opt technique in most of cases for different amounts of defocusing.

Fig. 7. Comparisons of experimental results from p-opt technique, i-opt technique, and proposed technique for (a) nearly-focused case, (b) slightly defocused case, and (c) severely defocused case.

To visually compare these different techniques, a more complex 3D statue is also measured. Fringe period is set to be T = 36 pixels in this experiment. The binary fringe patterns utilized in the experiment are shown in Fig. 3. Three deformed patterns generated by different techniques are shown Fig. 8. Figures 9(a)–9(c), 9(d)–9(f), and 9(g)–9(i) show the 3D results from the three techniques with a variety of amounts of defocusing. Table 1 shows the phase error acquired by taking the difference between 18-step shifted sinusoidal patterns and the phase recovered from defocused binary patterns. From the measurement results, we can notice that the measurement performances of all the binary patterns are degraded by noise, if the nearly-focused projector is used. And the p-opt technique and the proposed technique can slightly outperform the i-opt technique with less noise. With the amount of defocusing increasing, the phase errors decrease and measurement results turn smoother. The improvement with the p-opt technique is subtle, but obvious with the proposed technique and the i-opt technique. The proposed technique has less phase error and better measurement performance than the i-opt technique in most of cases. The experimental results are consistent with simulations. We find that the proposed technique can obtain pretty good phase performance and it ensures the robustness to different amounts of defocusing.

Fig. 8. Three defocused patterns obtained by utilizing p-opt technique, i-opt technique, and proposed technique, respectively.
Fig. 9. Measurement results of complex 3D statue. Panels (a)–(c), (d)–(f), and (g)–(i) show the 3D results obtained respectively by using p-opt technique, i-opt technique, and proposed technique, when projector is nearly focused, slightly defocused and more defocused respectively.
Table 1.

Phase RMS error (in unit rad) of measurement results.

.
6. Conclusions

In this paper, a genetic optimization framework is proposed to produce high-quality binary fringe patterns in the frequency domain. The harmonic noise can be easily eliminated in our framework based on frequency domain. We find that the proposed technique can consistently obtain substantial measurement performance improvement for various amounts of defocusing. It is verified that the proposed technique can obtain pretty good phase performance and it ensures the robustness to different amounts of defocusing.

Reference
[1] Zhang W Z Chen Z B Xia B F Lin B Cao X Q 2014 Chin. Phys. B 24 044212
[2] Qiao N S Cai X H Yao C M 2009 Chin. Phys. B 18 4881 https://doi.org/10.1088/1674-1056/18/11/044
[3] Zhang L Chen Q Zuo C Feng S J 2018 Appl. Opt. 57 1378 https://doi.org/10.1364/AO.57.001378
[4] Li B Zhang S 2017 Opt. Laser Eng. 96 117
[5] Zheng D L Da F P Kemao Q Seah H S 2016 Appl. Opt. 55 572
[6] Hyun J S Li B W Zhang S 2017 Opt. Eng. 56 074102 https://doi.org/10.1117/1.OE.56.7.074102
[7] Li B W Wang Y J Dai J F Lohry W Zhang S 2014 Opt. Lasers Eng. 54 236 https://doi.org/10.1016/j.optlaseng.2013.07.010
[8] Lu F Wu C D 2017 J. Eur. Opt. Soc.-Rapid Publ. 13 29 https://doi.org/10.1186/s41476-017-0055-7
[9] Wang Y J Jiang C F Zhang S 2017 Opt. Express 25 30177 https://doi.org/10.1364/OE.25.030177
10 Li B W An Y T Cappelleri D Zhang S 2017 Int. J. Intell. Robot. Applic. 1 86 https://doi.org/10.1007/s41315-016-0001-7
11 Su X Y Zhou W S Bally G V Vukicevic D 1992 Opt. Commun. 94 561 https://doi.org/10.1016/0030-4018(92)90606-R
12 Lei S Y Zhang S 2009 Opt. Lett. 34 3080 https://doi.org/10.1364/OL.34.003080
13 Ayubi G A Ayubi J A Martino J M D Ferrari J A 2010 Opt. Lett. 35 3682 https://doi.org/10.1364/OL.35.003682
14 Xian T Su X Y 2001 Appl. Opt. 40 1201 https://doi.org/10.1364/AO.40.001201
15 Schuchman L 1964 IEEE Trans. Commun. Technol. 12 162 https://doi.org/10.1109/TCOM.1964.1088973
16 Wang Y J Zhang S 2012 Appl. Opt. 51 6631 https://doi.org/10.1364/AO.51.006631
17 Dai J F Li B W Zhang S 2014 Opt. Lasers Eng. 53 79 https://doi.org/10.1016/j.optlaseng.2013.08.015
18 Dai J F Zhang S 2013 Opt. Laser Eng. 51 790 https://doi.org/10.1016/j.optlaseng.2013.02.003
19 Holl J H 1975 Adaptation in Natural and Artificial Systems Ann Arbor University Michigan Press 171 198
20 Lohry W Zhang S 2013 Opt. Lett. 38 540 https://doi.org/10.1364/OL.38.000540
21 Malacara D 2007 Optical Shop Testing 3 New York Wiley-Interscience 72 86
22 Zhang S 2016 High-speed 3D Imaging with Digital Fringe Projection Technique Boca Raton CRC Press 45 68
23 Lu F Wu C D Yang J K 2019 Opt. Commun. 430 246 https://doi.org/10.1016/j.optcom.2018.08.034
24 Rabiner L R Gold B 1975 Theory and Application of Digital Signal Processing Upper Saddle River Prentice-Hall 103 118
25 Zu Y X Zhou J Zeng C C 2010 Chin. Phys. B 19 119501 https://doi.org/10.1088/1674-1056/19/11/119501
26 Cai K Q Tang Y W Zhang X J Guan X M 2016 Chin. Phys. B 25 128904 https://doi.org/10.1088/1674-1056/25/12/128904